Computer Science
Use the Aggregate Method, the Banker's Method, or the Physicist's Method to perform Amortized Analysis.
- Charge extra for each cheap operation
- Save the extra charge as tokens in your data structure (conceptually)
- Use the tokens to pay for expensive operations...like an amortizing loan
Dynamic array: n calls to PushBack.
Charge 3 for each insertion: 1 token is the raw cost for insertion.
- Resize needed: To pay for moving the elements, use the token that's present on each element that needs to move
- Place one token on the newly-inserted element, and one token capacity/2 element prior
Example
- Empty array, size 0, capacity 0
- PushBack(a)
- Allocate array of size 1, put a into it, and give a a token. There's no other element to put a token on, so waste third token.
- PushBack(b)
- Allocate array of size 2, move a and pay for it with its token, update array and delete old one, put b in at cost of one. There are two tokens left. Give a and b each a token.
- PushBack(c)
- Allocate new array, copy a and b and pay with tokens, push in c, put token on c and a. (Capacity is 4, divided by 2 is 2, 2 elements prior is a.)
- PushBack(d)
- Put in d at cost of one, put token on d and b.
- PushBack(e)
- Allocate new array, move and pay for elements with tokens, push in e, put token on e and a.
- O(1) amortized cost for each PushBack. (It's a cost of 3 per.)
(ALGS201x)